/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2019年02月17日
*   描    述：
*   Copyright (C) 2019 All rights reserved.
*   
================================================================*/


#include <iostream>

using namespace std;

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int len = nums.size();
        if ( len <= 1 )
            return 0;

        int slow = nums[0], fast = nums[nums[0]];
        while( slow != fast ){
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        fast = 0;
        while(fast != slow){
            slow = nums[slow];
            fast = nums[fast];
        }
        
        return slow;
    }
};

class Solution {
    public int findDuplicate(int[] nums) {
        int i = 0;
        while (nums[i] != 0) {
            int x = nums[i];
            nums[i] = 0;
            i = x;
        }
        return i;
    }
}

